/**
 * 704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。

 * @param nums 
 * @param target 
 * @returns 
 */

function search(nums: number[], target: number): number {
    if (nums.length < 1) return -1;
    // 取中间位置
    let pos = Math.floor(nums.length / 2);
    // 设定区间左侧
    let left = 0;
    // 设定区间右侧
    let right = nums.length;
    // 遍历循环直到找到target
    while (nums[pos] !== target) {
        // 如果target大于当前的中间数，则设定区间左侧到当前中间位置，同时将当前位置移到新的区间位置中间
        if (target > nums[pos]) {
            left = pos;
            pos = Math.floor((pos + right) / 2);
        } else if (target < nums[pos]) {
            // 如果target小于当前的中间数，则设定区间右侧侧到当前中间位置，同时将当前位置移到新的区间位置中间
            right = pos;
            pos = Math.floor((pos + left) / 2);
        } else {
            // 相等则表示已找到
            break;
        }
        console.log("left: %s, right: %s, pos: %s", left, right, pos);
        // 如果左右位置相邻，则停止循环(可能找到，也可能没找到)
        if (right - left < 2) {
            break;
        }
    }
    // 当前数与target相等，则表示已找到，返回当前位置
    if (nums[pos] === target) return pos;
    // 反之则没找到，返回-1
    return -1;
}

const arr = [];
for (let i = 0; i < 10000; i++) {
    arr.push(i);
}

console.log("search target: 5, pos:", search([-1, 0, 5], 5));
console.log("search target: 1024, pos:", search(arr, 1024));

export { search };
